A free-form surface, which is used for the body of various industrial products such as a ship, a car, and an airplane, combines functionality with beauty, and is used for the design engineering of home electrical appliances and many other consumer products that require good form.
Recently, a 3D laser scanner collects high-density point group data speedily and easily, allowing an object shape to be measured accurately. For example, in the field of 3D modeling, a mock-up model manually created by a designer is measured by a 3D laser scanner to create CAD data, such as surface data necessary for producing products, based on the point group data and polygon data captured by a computer. This is the so-called the reverse engineering technique.
In general, a 3D model is represented on a computer using a polygon model or surface patches such as NURBS and B-Spline.
This polygon model, though efficient for performing shape processing such as a phase change, has a problem that a smooth surface cannot be represented because the polygon model is composed of flat surfaces. Another problem with the polygon model is that the more detailed the shape to be represented is, the larger the amount of data becomes.
A surface patch allows a smooth surface to be represented with a smaller number of control parameters, but the problem is that the patch shape is limited to squares and that it is difficult to ensure continuity between patches. To solve those problems, the subdivision method that combines the advantages of a polygon model with the advantages of a surface patch has attracted attention as a method efficient for the modeling of a free geometrical shape and, today, this method is already used commonly in the animation field.
The subdivision method refers to a method that divides the initial polygon mesh repeatedly and regularly to smooth its shape and, eventually, to produce a smooth surface. A surface created by the division is called a subdivision surface, and the final surface as a limit surface. Because of the characteristics that allow a smooth surface to be generated easily even for a model having any phase and because of the ability to define a smooth surface in any part, the subdivision method is now used in many fields such as modeling.
In the reverse engineering field, several methods have conventionally been proposed in which measured point group data is approximated to generate a surface by using the subdivision surface, B-Spline, NURBS, etc. In the conventional method for approximating or interpolating the data points of a point group, the operation processing is performed for serially obtaining the control points so that the distance error between the initial control point, obtained from the data points, and the generated surface is minimized. The operation for obtaining the control points is carried out by solving the linear determinant represented by AP=S where S is the column of the point group, P is the column of the control points for generating a surface approximating the point group, and A is the basis function matrix for defining the surface.
As one of the conventionally proposed approximation methods, the interpolation method for the Catmull-Clark subdivision surface for a polyhedron mesh, proposed by Halsted and his colleagues, is known (Non-Patent Document 1). This method requires the solution of not only a large-scale linear system but also a minimization problem for surface correction called fairing, resulting in a very high calculation cost.
Hoppe and his colleagues propose a method in which the approximation method of the loop subdivision surface for the data points of a point group is processed as a least-squares problem that, with a subdivided polygon mesh as a linearly-approximated subdivision surface, parameters are generated by orthogonally projecting from the points onto the surface and the distance between each point and the point on the linearly-approximated subdivision surface corresponding to the point is minimized (Non-Patent Document 2).
The method proposed by Hoppe and his colleagues (Non-Patent Document 2) generates parameters on the linearly approximated surface while Marinov and Kobbelt generate parameters on the limit surface using Stam's theory. However, the calculation of the control points requires a long time because a large-scale linear system must be solved (Non-Patent Document 8).
The method for fitting a loop subdivision surface to a point group using the SDM method (Squared Distance Minimization) is proposed. In this method, the object function, generated by locally quadratic-approximating a squared distance function from the initial surface is serially changed to transform the surface into a target surface. This method also solves a linear system and so requires a long time for the calculation (Non-Patent Document 9).
The method using the relation between a point group, specified for interpolating a B-Spline curve/surface, and the knot of the curve/surface generated by the point group is proposed. In this method, the distance between the given point group and the knot is used as a motion vector, the control point is moved for the length corresponding to the vector, and this processing is repeated until the distance between the point and the knot becomes 0. However, because double control points are used at both ends, this method cannot be used for CAD data. In some cases, a swell may be generated because the difference vector with the knot is used (Non-Patent Document 10).
Non-Patent Document 1: M. Halsted, M. Kass and T. DeRose. Efficient, fair interpolation using Catmull-Clark surfaces. In Eugene Fiume, editor. Proceedings of SIGGRAPH1993, pages 47-61. ACM, ACM Press/ACM SIGGRAPH, 1993
Non-Patent Document 2: H. Hoppe, T. DeRose, T. Duchamp and M. Halsted. Piecewise smooth surface reconstruction. In Proceedings of SIGGRAPH 1994, pages 47-61. ACM, ACM Press/ACM SIGGRAPH, 1994
Non-Patent Document 3: M. Garland and P. S. Heckbert. Surface simplification using quadric error metrics. In Proceedings of ACM SIGGRAPH 97, 209-216.
Non-Patent Document 4: C. T. Loop. Smooth subdivision surface based on triangle. Masters thesis, Department of Mathematics. University of Utha.1987/.
Non-Patent Document 5: E. Catmull and J. Clark. Recursively generated b-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 10(6):350-355, 1987.
Non-Patent Document 6: D. Doo and M. Sabin. Behavior of recursive division surfaces near extraordinary points. Computer-Aided Design, 10(6):356-360, 1978.
Non-Patent Document 7: G. M. Chaikin. An algorithm for high-speed curve generation. Computer Graphics and Image Processing, 3:346-349, 1974.
Non-Patent Document 8: M. Marinov and L. Kobbelt, Optimization methods for scattered data approximation with subdivision surface, Graphical Models 67, 2005, 452-473.
Non-Patent Document 9: K-S. D. Cheng, Wang. W, Qin. H, K-Y. K. Wong, Yang. H and Liu. Yang. 2007. Design and analysis of optimization methods for subdivision surface fitting. IEEE Transaction on Visualization and Computer Graphics 13, 5, 878-890.
Non-Patent Document 10: Lin. H, Wang. G, and Dong. C. 2003. Constructing iterative non-uniform B-spline curve and surface to fit data points. Science in China 33, 912-923.